/**
 * @a https://leetcode.cn/problems/minimum-genetic-mutation/description/
 */

#include "../../common.h"

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        static const char DNA[5] = "ATCG";
        if(startGene == endGene) return 0;
        unordered_set<string> contain_bank(bank.begin(), bank.end());
        if(contain_bank.count(endGene) == 0) return -1;
        unordered_set<string> visited;

        queue<string> que;
        que.push(startGene);
        visited.insert(startGene);
        int cnt = 0;
        while (que.size()) {
            int sz = que.size();
            ++cnt;
            while (sz--) {
                string cur_str = que.front();
                que.pop();
                for(int i = 0; i < 8; ++i){
                    string tmp = cur_str;
                    for (auto item : DNA) {
                        tmp[i] = item;
                        if (!visited.count(tmp) &&
                            contain_bank.count(tmp)) {
                            if(tmp == endGene) return cnt;
                            que.push(tmp);
                            visited.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};